#pragma once
#include <Windows.h>
template <typename TYPE>
struct LLNode
{
	/** data stored by this class */
	TYPE data;
	bool used;
	/** the next node in the linked list */
	LLNode<TYPE> * next;
	/**
	* 'next' should be NULL (0) after this constructor is called
	* @param a_value will be this linked list node's data value
	*/
	LLNode(TYPE a_value)
		:data(a_value),next(0),used(0)
	{
	}
	/** @return the number of {@link LLNode}s following this one */
	int size()
	{
		int number = 0;
		LLNode<TYPE> * iter = this;
		while( iter !=0 )
		{
			number++;
			iter = iter->next;

		}
		return number;
	}
	/** @return a node in this linked list, a_index number of nodes away from this one */
	LLNode<TYPE> * getNode(int a_index)
	{
		LLNode<TYPE> * iter = this;
		for(int i = 0; i < a_index; ++i)
		{
			iter = iter->next;
		}

		return iter;
	}
	/** @return the value at the node that could be referenced by getNode(a_index) */
	TYPE get(int a_index)
	{
		return getNode(a_index)->data;
	}
	/** @return the last node in the linked list starting at this node */
	LLNode<TYPE> * getLast()
	{
		//LLNode * temp = this;
		//if(temp->next != NULL)
		//{
		//	temp = temp->next;
		//}
		//
		//return temp->next;
		return getNode(size()-1);
	}
	/** @param a_node a node to add to the end of this linked list */
	void addNode(LLNode<TYPE> * a_node)
	{
		getLast()->next = a_node;
		//a_node->next = 0;
	}
	/** @param a_value a *new* node will be added to the end of the linked list with this value */
	void add(TYPE a_value)
	{
		LLNode * temp = new LLNode(a_value);
		addNode(temp);
	}
	bool getUsed(int a_index)
	{
		return getNode(a_index)->used;
	}
	void changeUsed(int a_index)
	{
		this->used = true;
	}
};


template<typename TYPE>
class LinkedList
{
private:
	LLNode<TYPE> * head;
public:
	/** a newly created LinkedList should have a NULL (0) head, and return true when isEmpty() is called */
	LinkedList()
	{
		head = NULL;
	}
	LinkedList(TYPE a_value)
	{
		head = new LLNode<TYPE>(a_value);
	}
	/** @return true if the head is NULL (0), meaning there are no elements in the list */
	bool isEmpty()
	{
		if(head == 0)
		{ return true;}
		else
		{ return false;}
	}
	/** @return the head node, or NULL (0) if the list is empty */
	LLNode<TYPE> * getFirst()
	{
		if(isEmpty())
		{return 0;}
		else
		{return head;}
	}
	/** @return -1 if the given node is not in the linked list, otherwise returns the index where the node is */
	int indexOfNode(LLNode<TYPE> * a_node)
	{
		for(int i = 0; i < size();++i)
		{
			if(a_node == getNode(i))
			{
				return i; 
			}
		}
		return -1;

	}
	/** @return -1 if the given value is not held by a node in the linked list, otherwise returns the first index where the value is */
	//Must overload operator== if datatype isn't standard
	int indexOf(TYPE a_value)
	{
		for(int i = 0; i<size(); ++i)
		{
			if(get(i) == a_value)
			{return i;}

			else if(getNode(i)->next == NULL)
			{
				break;
			}
		}
		return -1;
	}
	/** adds the given node as the head, or to the end of the list that the head begins */
	void addNode(LLNode<TYPE> * node)
	{
		if(isEmpty()==true)
		{
			head = node;
		}
		else
		{
			head->addNode(node);
		}
	}
	/** adds a *new* node with the given value as the head, or to the end of the list that the head begins */
	void add(TYPE a_value)
	{

		if(head == NULL)
		{
			LLNode<TYPE> * temp = new LLNode<TYPE>(a_value);
			head = temp;
		}
		else
		{
			head->add(a_value);
		}
	}
	/** @return the node whose index is their position on the head's linked list chain */
	LLNode<TYPE> * getNode(int a_index)
	{

		return head->getNode(a_index);
	}
	/** @return the last node in the linked list, or NULL (0) if the list is empty */
	LLNode<TYPE> * getLast()
	{

		return head->getLast();
	}
	/** @return the value of the node whose index is their position on the head's linked list chain */
	//Must overload operator== if datatype isn't standard
	TYPE get(int a_index)
	{
		return head->get(a_index);
	}
	/** @return the number of nodes in the linked list starting at head */
	int size()
	{
		return head->size();
	}
	/** @return the head node. makes the new head point at the node following the head. should also clear the old head's next */
	LLNode<TYPE> * removeHeadNode()
	{
		LLNode<TYPE> * temp = head;
		head = head->next;
		temp->next = NULL;
		return temp;
	}
	/** @return the node at the given index, which is removed from the list. the rest of the list should continue without the midshould also clear the removed node's next */
	LLNode<TYPE> * removeNode(int a_index)
	{
		LLNode<TYPE> * temp;
		if(a_index)
		{
			temp = head->getNode(a_index);
			head->getNode(a_index-1)->next = temp->next;
			temp->next = NULL;
		}
		else
			temp = removeHeadNode();
		return temp;
	}
	/** functions as removeNode(int), except it also calls *delete* on the removed node */
	void remove(int a_index)
	{
		delete removeNode(a_index);
	}
	/** makes the given node the new head, and sets the old head as the new head's next */
	void insertHeadNode(LLNode<TYPE> * a_node)
	{
		LLNode<TYPE> * temp = head;
		head=a_node;
		head->next = temp;
	}
	/** inserts the given node into the given index, moving the old node in that index behind the newly inserted node */
	void insertNode(int a_index, LLNode<TYPE> * a_node)		
	{
		LLNode<TEMP> * temp;
		if(a_index && (a_index<size()))
		{
			temp = head->getNode(a_index);
			getNode(a_index-1)->next = a_node;
			a_node->next=temp;
		}
		else if(a_index>=size())
			addNode(a_node);
		else
			insertHeadNode(a_node);
	}
	/** inserts the a *new* node with the given value into the given index, moving the old node in that index behind the newly inserted node */
	void insert(int a_index, TYPE a_value)
	{
		LLNode<TYPE> * temp;
		LLNode<TYPE> * newnode = &LLNode<TYPE>(a_value);
		if(a_index && get(a_index))
		{
			temp=head->getNode(a_index);
			getNode(a_index-1)->next = newnode;
			newnode->next = temp;
		}
		else
		{
			insertHeadNode(newnode);
		}	
	}

	// extra credit
	/** @return true if the specified elements have exchanged position in the list without altering node locations in memory (only pointers changed) */
	bool swap(int a_indexA, int a_indexB)
	{
		//If 'a' is in the index after 'b' then remove 'a' first
		if(a_indexA > a_indexB)
		{
			//create a pointer so we don't lose 'a' or 'b' after removing
			LLNode<TYPE> * a = removeNode(a_indexA);
			LLNode<TYPE> * b = removeNode(a_indexB);
			insertNode(a_indexB, a);
			insertNode(a_indexA, b);
		}
		//If 'b' is in the index after 'a' then remove 'b' first
		else if(a_indexA < a_indexB)
		{
			LLNode<TYPE> * b = removeNode(a_indexB);
			LLNode<TYPE> * a = removeNode(a_indexA);
			insertNode(a_indexA, b);
			insertNode(a_indexB, a);
		}
		return true;
	}
	/** @return true if the specified list was sorted in ascending order without changing memory locations of node data (only pointers changed) */
	bool sortAscending()
	{
		insertSort(this,size());
		return true;
	}
	void insertSort(LinkedList<TYPE> * list, int length)
	{
		int lastcheck = 0;
		//int temp;
		int j;
		for(int i = 0; i<length;++i)
		{
			j=i;
			//temp = i;
			if(i!=0)
			{
				for(int k = i; k > -2; k--)
				{
					lastcheck =k + 1;
					if(list->getNode(i)->data > list->getNode(k)->data)
					{
						break;
					}
				}

				while(j > lastcheck)
				{
					list->swap(j,j-1);
					j--;
				}
			}
		}
	};
	bool getUsed(int a_index)
	{
		return getNode(a_index)->used;
	}
	void changeUsed(int a_index)
	{
		head->changeUsed(a_index);
	}
};

